#include <iostream>
#include <vector>
using namespace std;
// 搜索区间为[l,r)
int BinaryFindAny1(vector<int>& v, int target) {
  int len = v.size();
  int l = 0;
  int r = len;
  int mid;
  while (l < r) {
    mid = l + (r - l) / 2;
    if (v[mid] < target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid;
    else
      return mid;
  }
  return -1;
}
int BinaryFindLeft1(vector<int>& v, int target) {
  int len = v.size();
  int l = 0;
  int r = len;
  int mid;
  while (l < r) {
    mid = l + (r - l) / 2;
    if (v[mid] < target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid;
    else
      r = mid;
  }
  return v[r] == target ? r : -1;
}
int BinaryFindRight1(vector<int>& v, int target) {
  int len = v.size();
  int l = 0;
  int r = len;
  int mid;
  while (l < r) {
    mid = l + (r - l) / 2;
    if (v[mid] < target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid;
    else
      l = mid + 1;
  }
  return v[r - 1] == target ? r - 1 : -1;
}

// 搜索区间为[l,r]
int BinaryFindAny2(vector<int>& v, int target) {
  int len = v.size();
  int l = 0;
  int r = len - 1;
  int mid;
  while (l <= r) {
    mid = l + (r - l) / 2;
    if (v[mid] < target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid;
    else
      return mid;
  }
  return -1;
}
int BinaryFindLeft2(vector<int>& v, int target) {
  int len = v.size();
  int l = 0;
  int r = len - 1;
  int mid;
  while (l <= r) {
    mid = l + (r - l) / 2;
    if (v[mid] < target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid - 1;
    else
      r = mid - 1;
  }
  return v[l] == target ? l : -1;
}
int BinaryFindRight2(vector<int>& v, int target) {
  int len = v.size();
  int l = 0;
  int r = len - 1;
  int mid;
  while (l <= r) {
    mid = l + (r - l) / 2;
    if (v[mid] < target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return v[r] == target ? r : -1;
}

int main() {
  vector<int> v{1, 2, 3, 3, 4, 10, 10, 10, 10, 10, 89, 90};
  int target = 10;
  cout << BinaryFindAny1(v, 10) << endl;
  cout << BinaryFindLeft1(v, 10) << endl;
  cout << BinaryFindRight1(v, 10) << endl;
  cout << "------------------------------" << endl;
  cout << BinaryFindAny2(v, 10) << endl;
  cout << BinaryFindLeft2(v, 10) << endl;
  cout << BinaryFindRight2(v, 10) << endl;
  return 0;
}